package _09_高频题;

/**
 * https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
 * @Author: haogege
 * @Date: 2021/9/3
 */
public class 剑指_Offer_62_圆圈中最后剩下的数字 {

    // 约瑟夫环问题 f(n, m) = (f(n - 1, m) + m) % n;
    public int lastRemaining2(int n, int m) {
        return n == 1? 0: (lastRemaining(n - 1, m) + m) % n;
    }

    // 迭代
    public int lastRemaining(int n, int m) {
        int res = 0;
        // i是数据规模，表示还有多少个人，如果是一个人的话，就是0，当前位置
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }

    // 如果是从编号1开始，而不是编号0
    public int lastRemaining1(int n, int m) {
        int res = 0;
        // i是数据规模，表示还有多少个人，如果是一个人的话，就是0，当前位置
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        // 从编号1开始
        return res + 1;
    }
}
